package com.Dec_eIGHT;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 435. 无重叠区间
 * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/non-overlapping-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/11/08 19:54
 */

public class Solution435 {

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int cnt=1;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0]>=intervals[i-1][1]){
                cnt++;
            }else {
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return intervals.length-cnt;
    }

    public static void main(String[] args) {
        Solution435 solution435=new Solution435();
        System.out.println(solution435.eraseOverlapIntervals(new int[][]{{1,2},{2,3},{3,4},{1,3}}));
    }

}
